package _17_graph;

import org.junit.Test;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author: mornd
 * @dateTime: 2023/6/25 - 11:10
 * 使用优先级队列改进 狄克斯特拉 算法
 */
public class Dijkstra2 {
    @Test
    public void test() {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");

        v1.edges = List.of(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14));
        v3.edges = List.of(new Edge(v4, 11), new Edge(v6, 2));
        v2.edges = List.of(new Edge(v4, 15));
        v6.edges = List.of(new Edge(v5, 9));
        v4.edges = List.of(new Edge(v5, 6));
        v5.edges = List.of();

        List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);

        dijkstra(v1, graph);

        for (Vertex vertex : graph) {
            System.out.println("name=" + vertex.name + ",dist=" + vertex.dist + ",from=" + (vertex.prev != null ? vertex.prev.name : null));
        }
    }

    private void dijkstra(Vertex source, List<Vertex> graph) {
        // 小顶堆结构，每次取出的都是集合中 dist 最小的
        PriorityQueue<Vertex> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.dist));
        source.dist = 0;
        for (Vertex vertex : graph) {
            queue.offer(vertex);
        }

        while (!queue.isEmpty()) {
            System.out.println(queue);
            Vertex curr = queue.peek();
            if (!curr.visited) {
                // 由于队列中会出现重复顶点，需要根据顶点的属性来判断是否第一次访问
                updateNeighborsDist(curr, queue);
                curr.visited = true;
            }
            queue.poll();
        }
    }

    private void updateNeighborsDist(Vertex curr, PriorityQueue<Vertex> queue) {
        for (Edge edge : curr.edges) {
            Vertex neighbor = edge.linked;
            if (!neighbor.visited) { // visited为false，表示已经访问过了，既然访问过了那么它的dist已是最短，无需再调整了
                int newDist = curr.dist + edge.weight;
                if (newDist < neighbor.dist) {
                    neighbor.dist = newDist;
                    neighbor.prev = curr;
                    // 重新调整优先级
                    queue.offer(neighbor);
                }
            }
        }
    }
}
